package my15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SuandFa15 {
    public List<List<Integer>> threeSum(int[] nums) {
        //第一步，先将代码排序，这样会提高代码的效率，因为题目要求三数和为0，我们知道当从小到大排序时，当三个数中最小的数
        //大于0的时候，不管怎么样都不会有结果是零的情况，将代码排序会方便我们判断。
        Arrays.sort(nums);
        //第二步，我们新建一个List集合存储所有最后结果为0的三个数。
        List<List<Integer>> its = new ArrayList<>();
        int length = nums.length;
        //第三步，我们可以将最左面的指针固定，其他两个指针作为双指针。
        //最左面的指针i使用for循环遍历，循环终止条件是i <= nums.length-2
        for (int i = 0; i < length-2; i++) {
            //当此时i指针对应的数据大于0时直接跳出循环，因为最左面的指针作为最小的指针，当nums[i]>0时,
            //其他的两个指针对应的索引均大于0，不符合条件nums[i] + nums[j] + nums[k] == 0
            if (nums[i] > 0){
                break;
            }
            //若下一次的i指针和当前i指针相同的话跳出当前循环。
            //同时需要注意当前的i指针要大于0也就是说第一次循环时不走这一个判断条件
            if (i >0 && nums[i] == nums[i-1]){
                continue;
            }
            //双指针的左右指针定
            int j = i+1;
            int k = length-1;

            while( j < k){
                int sum = nums[i] + nums[j] + nums[k];
                //当结果 == 0时
                if (sum == 0){
                    //添加进入数组中
                    its.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[k])));
                    //判断下一次与该左右指针相同的跳出循环,并执行j++ ，k --
                    while(j < k && nums[j] == nums[j+1]){
                        j++;
                    }
                    j++;
                    while(j < k && nums[k] == nums[k-1]){
                        k--;
                    }
                    k--;
                }
                //当sum的值小于0时，说明当前的数还不够大所以需要将左指针向前移动一位，并且
                //当移动之前的值等于移动之后的值时，忽略这一次的值，并向前移动一位。
                if (sum < 0){

                    while(j < k && nums[j] == nums[j+1]){
                        j++;
                    }
                    j++;
                }
                //当sum的值大于0时，反之亦然
                if (sum > 0){
                    while(j < k && nums[k] == nums[k-1]){
                        k--;
                    }
                    k--;
                }
            }
        }
        return its;
    }

    public static void main(String[] args) {
        SuandFa15 suandFa15 = new SuandFa15();
        int[] suanfa15demo = {-1,0,1,2,-1,-4};
        suandFa15.threeSum(suanfa15demo);
    }
}
